// https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
// 114. 二叉树展开为链表
// 给定二叉树的根节点 root，请你将它展开为一个单链表。展开后的单链表应该同样使用 TreeNode，
// 其中 right 子指针指向链表中下一个节点，而左指针始终为 null
// 展开后的单链表应该与二叉树先序遍历顺序相同。
// 使用原地算法（O(1) 额外空间）展开这棵树
import { TreeNode } from '../utils/index.ts';
function flatten(root: TreeNode | null): void {
    if (root === null) return;

    let cur: TreeNode | null = root;

    while (cur !== null) {
        if (cur.left !== null) {
            const prev = findPrev(cur.left);
            [prev.right, cur.right, cur.left] = [cur.right, cur.left, null];
        }
        cur = cur.right;
    }

    function findPrev(root: TreeNode): TreeNode {
        while (root.right !== null) {
            root = root.right;
        }
        return root;
    }
}
